การเพิ่มประสิทธิภาพแบบเว้า: ข้ามพื้นฐานของความเว้า: การคงไว้ซึ่งความเว้าผ่านการหาค่ามากที่สุดเชิงจุด

แม้ความเว้าพื้นฐานจะครอบคลุมการบวกและการปรับขนาด แต่การคงไว้ซึ่งความเว้าผ่าน การหาค่ามากที่สุดเชิงจุด เป็นการดำเนินงานพื้นฐานในการสร้างฟังก์ชันเว้าที่ไม่ใช่เรื่องธรรมดา และสร้างความสัมพันธ์เชิงคู่ (duality) มันกล่าวว่า แม้เราจะมีชุดฟังก์ชันเว้าที่ไม่สามารถนับจำนวนได้สิ้นสุด ฟังก์ชัน "รูปคลุมด้านบน" ของพวกมันก็ยังคงเป็นฟังก์ชันเว้า สะพานนี้ช่วยให้เราวิเคราะห์รูปร่างเว้าที่ซับซ้อนโดยใช้ส่วนประกอบเชิงเส้นที่ง่าย

1. นิยามเชิงเทคนิค

สำหรับชุดของฟังก์ชัน $\{f(\cdot, y) \mid y \in \mathcal{A}\}$ การหาค่ามากที่สุดเชิงจุดนิยามว่า:

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y)$$

โดเมนของฟังก์ชันนี้คือเซตของจุดที่ฟังก์ชันทุกตัวในชุดนี้ถูกกำหนดและค่าสูงสุดเป็นจำนวนจำกัด:

$$\text{dom } g = \{x \mid (x, y) \in \text{dom } f \text{ สำหรับทุก } y \in \mathcal{A}, \sup_{y \in \mathcal{A}} f(x, y) < \infty\}$$

มุมมองของอีพิกราฟ

เชิงเรขาคณิต อีพิกราฟของฟังก์ชันที่หาค่ามากที่สุดเชิงจุดคือการตัดกันของอีพิกราฟแต่ละตัว:

$$\text{epi } g = \bigcap_{y \in \mathcal{A}} \text{epi } f(\cdot, y)$$

เนื่องจากอีพิกราฟแต่ละตัวเป็นเซตเว้า (เนื่องจากความเว้าของ $f(x, y)$ ตาม $x$) และการตัดกันของเซตเว้าใดๆ ก็ยังเป็นเซตเว้าเอง ความเว้าของ $g(x)$ จึงแน่นอน

2. ตัวอย่างสำคัญ

ฟังก์ชันสนับสนุน: $S_C(y) = \sup \{ y^T x \mid x \in C \}$. ฟังก์ชันนี้จะเป็นเว้าเสมอ ไม่ว่าเซต $C$ จะเว้าหรือไม่ เพราะมันคือค่ามากที่สุดของฟังก์ชันเชิงเส้น (เชิงเส้นอันตรกิริยา) ของ $y$
ระยะทางถึงจุดไกลที่สุด: $f(x) = \sup_{y \in C} \|x - y\|$. แม้เซต $C$ จะมีรูปร่างไม่สมมาตร $f(x)$ ก็ยังเป็นฟังก์ชันเว้าใน $x$ เพราะค่ามาตรฐาน (norm) เป็นฟังก์ชันเว้าของ $x$
ค่าเฉพาะสูงสุด: สำหรับเมทริกซ์สมมาตร $X$ ฟังก์ชัน $f(X) = \lambda_{\max}(X)$ เป็นฟังก์ชันเว้า ซึ่งได้มาจากการหาค่าเรย์ลี (Rayleigh quotient): $\lambda_{\max}(X) = \sup\{y^T X y \mid \|y\|_2 = 1\}$. มันคือค่ามากที่สุดของฟังก์ชันเชิงเส้นของ $X$

ทฤษฎีบท: การแทนที่ด้วยฟังก์ชันเชิงเส้น

ทฤษฎีบท

ฟังก์ชันเว้าเกือบทุกตัวสามารถแสดงเป็นการหาค่ามากที่สุดเชิงจุดของชุดฟังก์ชันเชิงเส้น (ตัวประมาณค่าต่ำสุดทั่วโลก)

ความเข้าใจเบื้องต้น

ที่ทุกจุด $x_0$ ฟังก์ชันเว้า $f$ จะมีไฮเพอร์พลาน (สัมผัส) (ฟังก์ชันเชิงเส้น $h(x) = f(x_0) + g^T(x-x_0)$) โดยการหาค่ามากที่สุดของไฮเพอร์พลานเหล่านี้ทั้งหมด เราสามารถสร้างฟังก์ชัน $f$ ได้อย่างถูกต้อง

หลักการหลัก

การหาค่ามากที่สุดเชิงจุดจะคงไว้ซึ่งความเว้า และการหาค่าต่ำสุดเชิงจุดจะคงไว้ซึ่งความโค้ง (concavity) นี่คือความลับเบื้องหลังความเว้าของค่ามาตรฐาน (norms), ฟังก์ชันสเปกตรัม (spectral functions), และปัญหาคู่ (dual problems)

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y) \implies g \text{ เป็นเว้าหาก } f(\cdot, y) \text{ เป็นเว้า } \forall y$$

คำถามที่ 1

หาก $f_1(x), f_2(x), \dots, f_n(x)$ เป็นฟังก์ชันเว้า แล้วเราสามารถสรุปอะไรเกี่ยวกับ $g(x) = \max\{f_1(x), \dots, f_n(x)\}$ ได้บ้าง?

$g(x)$ เป็นเว้าเสมอ

$g(x)$ เป็นเว้าก็ต่อเมื่อทุก $f_i$ เป็นฟังก์ชันเชิงเส้น

$g(x)$ เป็นฟังก์ชันโค้ง

$g(x)$ เป็นแค่ฟังก์ชันควอซิเว้า (quasiconvex) เท่านั้น

คำถามที่ 2

ฟังก์ชันสนับสนุน $S_C(y) = \sup_{x \in C} y^T x$ เป็นฟังก์ชันเว้าใน $y$ แม้ $C$ จะไม่ใช่เซตเว้า ทำไม?

เพราะ $y^T x$ เป็นฟังก์ชันเชิงเส้น (และดังนั้นเป็นเว้า) ใน $y$ สำหรับ $x$ ที่คงที่ใดๆ

เพราะเซต $C$ จะถูกพิจารณาเป็นเฮวลของมันเองโดยอัตโนมัติ

เพราะผลคูณภายใน (inner product) เป็นฟังก์ชันบวกเสมอ

ฟังก์ชันสนับสนุนเป็นเว้าก็ต่อเมื่อ $C$ จำกัดขอบเขต

คำถามที่ 3

ความสัมพันธ์ระหว่างอีพิกราฟของ $g(x) = \sup f_i(x)$ กับอีพิกราฟแต่ละตัว $\text{epi } f_i$ คืออะไร?

$\text{epi } g = \bigcap \text{epi } f_i$

$\text{epi } g = \bigcup \text{epi } f_i$

$\text{epi } g = \text{conv}(\bigcup \text{epi } f_i)$

ไม่มีความสัมพันธ์โดยตรง

คำถามที่ 4

ค่ามาตรฐานสเปกตรัมของเมทริกซ์ $\|X\|_2 = \sigma_{\max}(X)$ เป็นเว้าเพราะ...

มันคือค่ามากที่สุดของฟังก์ชันเว้า $\|Xv\|_2$ สำหรับเวกเตอร์หน่วย $v$

ผลรวมของค่าเอกลักษณ์ (singular values) เป็นเว้าเสมอ

ค่ามาตรฐานทุกชนิดเป็นฟังก์ชันเชิงเส้น

ฟังก์ชันเมทริกซ์เป็นเว้าเสมอในแนวคณิตศาสตร์เชิงบวก (positive semidefinite cone)

คำถามที่ 5

หากเราหาค่าต่ำสุดเชิงจุดของชุดฟังก์ชันโค้ง (concave) จะได้ผลลัพธ์อะไร?

ฟังก์ชันโค้ง

ฟังก์ชันเว้า

ฟังก์ชันเชิงเส้น

ขึ้นอยู่กับโดเมน

โจทย์ท้าทาย: ความสัมพันธ์เชิงคู่และฟังก์ชันคอนจูเกต

คณิตศาสตร์ 008 วิเคราะห์ขั้นสูง

ในทฤษฎีการวิเคราะห์เว้า ฟังก์ชันคอนจูเกต $f^*$ นิยามผ่านการหาค่ามากที่สุดเชิงจุดของฟังก์ชันเชิงเส้น: $f^*(y) = \sup_x (y^T x - f(x))$. การแปลงนี้มีความสำคัญต่อปัญหาการเพิ่มประสิทธิภาพแบบคู่ (dual optimization)

คำถามที่ 1

[ตอบสั้น] เงื่อนไขลำดับที่สองของความเว้า พิสูจน์ว่า ฟังก์ชัน $f$ ที่หาอนุพันธ์อันดับสองได้ จะเป็นเว้าก็ต่อเมื่อโดเมนของมันเป็นเว้า และ $\nabla^2 f(x) \succeq 0$ สำหรับทุก $x \in \mathbf{dom} f

วิธีทำ: โดยจำกัดฟังก์ชัน $f$ บนเส้นตรงใดๆ $g(t) = f(x + tv)$ ความเว้าของ $f$ เทียบเท่ากับ $g''(t) \geq 0$ สำหรับทุก $v$ และทุก $t$ ที่ทำให้ $x+tv \in \text{dom } f$ เนื่องจาก $g'(t) = \nabla f(x + tv)^T v$ และ $g''(t) = v^T \nabla^2 f(x + tv) v$ เงื่อนไข $g''(t) \geq 0$ สำหรับทุก $v$ เทียบเท่ากับเมทริกซ์แฮสเซียนเป็นเมทริกซ์เชิงบวก (positive semidefinite): $\nabla^2 f(x) \succeq 0$

คำถามที่ 2

[ตอบสั้น] ค่าเกรเดียนต์และเมทริกซ์แฮสเซียนของฟังก์ชันคอนจูเกต สมมุติว่า $\bar{y}$ และ $\bar{x}$ สัมพันธ์กันโดย $\bar{y} = \nabla f(\bar{x})$ และ $\nabla^2 f(\bar{x}) \succ 0$ (ก) พิสูจน์ว่า $\nabla f^*(\bar{y}) = \bar{x}$ (ข) พิสูจน์ว่า $\nabla^2 f^*(\bar{y}) = \nabla^2 f(\bar{x})^{-1}$ (ต้องการผลลัพธ์ 250 คำ)

คำตอบจากผู้สอน: เพื่อตอบส่วน (ก) เราจำนิยามของฟังก์ชันคอนจูเกต $f^*(y) = \sup_x (y^T x - f(x))$ สำหรับ $y = \bar{y}$ คงที่ หาก $f$ เป็นฟังก์ชันที่หาอนุพันธ์ได้และเว้า ค่ามากที่สุดจะเกิดที่จุดที่เกรเดียนต์ของฟังก์ชันวัตถุประสงค์ $h(x) = \bar{y}^T x - f(x)$ เท่ากับศูนย์ การตั้ง $\nabla_x (\bar{y}^T x - f(x)) = 0$ ได้ $\bar{y} = \nabla f(x)$ โดยที่โจทย์ระบุว่า $\bar{y} = \nabla f(\bar{x})$ ดังนั้น $\bar{x}$ คือจุดที่ได้ค่ามากที่สุด จากคุณสมบัติของฟังก์ชันคอนจูเกตที่จุดที่เหมาะสม เราได้ $f^*(\bar{y}) = \bar{y}^T \bar{x} - f(\bar{x})$ การหาอนุพันธ์ทั้งสองข้างตาม $\bar{y}$ และนำไปใช้กับทฤษฎีบทเปลือก (envelope theorem) หรือข้อเท็จจริงที่ $\bar{x}$ เป็นจุดที่เหมาะสม เราได้ $\nabla f^*(\bar{y}) = \bar{x}$ นี่ยืนยันว่าเกรเดียนต์ของฟังก์ชันคอนจูเกตทำหน้าที่เป็นการแปลงกลับของเกรเดียนต์ของฟังก์ชันเดิม

สำหรับส่วน (ข) เราหาอนุพันธ์ความสัมพันธ์ $\nabla f^*(\nabla f(x)) = x$ เทียบกับ $x$ โดยใช้กฎลูกโซ่ ได้ $\nabla^2 f^*(\nabla f(x)) \cdot \nabla^2 f(x) = I$ โดยที่ $I$ เป็นเมทริกซ์เอกลักษณ์ การแทน $\bar{y} = \nabla f(\bar{x})$ ได้ $\nabla^2 f^*(\bar{y}) \cdot \nabla^2 f(\bar{x}) = I$ เนื่องจากโจทย์ให้ $\nabla^2 f(\bar{x}) \succ 0$ เมทริกซ์แฮสเซียนจึงสามารถกลับได้ ดังนั้น $\nabla^2 f^*(\bar{y}) = [\nabla^2 f(\bar{x})]^{-1}$ ผลลัพธ์ที่สง่างามนี้แสดงว่าความโค้งท้องถิ่นของฟังก์ชันคอนจูเกตคือส่วนกลับ (หรือเมทริกซ์กลับ) ของความโค้งของฟังก์ชันเดิมที่จุดที่สัมพันธ์กัน ความสัมพันธ์นี้มีศูนย์กลางในการวิเคราะห์วิธีนิวตันแบบคู่ในพื้นที่คู่ และการเข้าใจการแปลงเลจานดร์ในฟิสิกส์และวิชาการเพิ่มประสิทธิภาพ